/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***归并排序          P67                       ***/
/***C++ 实现版本    written by Daniel           ***/
#include <iostream>
//用于获取系统时间
#include <ctime>
//用于生成随机数
#include <cstdlib>
using std::cout;
using std::endl;
#define MAX 20

void printArr(int *arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        std::cout << arr[i] << "\t";
    }
    std::cout << std::endl;
}

/*
作用：合并两个有序数列
参数：arr 待合并的数列
返回值： left 数列的左端  mid 数列的中间  right 数列的右端 temp返回的有序数列，传出参数
*/
void merge(int *arr, int left, int mid, int right, int *temp)
{
    int i=left;
    int j=mid+1;
    int t=0;
    //int *temp=new int[right-left+1];
    while((i<=mid)&&(j<=right)){
        if ((arr[i]<=arr[j])){
            temp[t]=arr[i];
            t++;
            i++;
        }
        else{
            temp[t]=arr[j];
            t++;
            j++;
        }
    } 
    while (i<=mid)
    {
        temp[t]=arr[i];
        i++;
        t++;
    }
    while (j<=right)
    {
        temp[t]=arr[j];
        j++;
        t++;
    }
    //并不是每次都拷贝8个,分治算法最开始是2个，4个，...一直到n个
    int tempLeft=left;
    t=0;
    cout<<"left="<<left<<"\t";
    cout<<"right="<<right<<endl;
    while(tempLeft<=right){
        arr[tempLeft]=temp[t];
        tempLeft++;
        t++;
    }    
}

void mergeSort(int *arr, int left, int right, int *temp)
{
   if (left<right){
       int mid=(left+right)/2;
       mergeSort(arr,left,mid,temp);
       mergeSort(arr,mid+1,right,temp);
       merge(arr,left,mid,right,temp);
   }
}

int main(int argc, char **argv)
{
    //使用系统时间生成一个随机数种子
    // srand(time(NULL));
    int *array = new int[MAX];
    int *temp=new int[MAX];
    for (int i = 0; i < MAX; i++)
    {
        array[i] = rand() % MAX;
        // cout<<array[i]<<endl;
    }
    printArr(array, MAX);
    time_t now = time(NULL);
    std::cout << "now=" << now << std::endl;
    mergeSort(array,0,MAX-1,temp);
    printArr(array, MAX);
    time_t newNow = time(NULL);
    std::cout << "newNow=" << newNow << std::endl;
    std::cout << "一共花了" << newNow - now << "秒" << endl;
    delete[] array;
    delete[] temp;
    return 0;
}